package tree.test114;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/17 8:52
 */
public class Solution1 {

    public void flatten(TreeNode root) {
        if (root == null) return;
        if (root.left == null) {
            flatten(root.right);
        } else {
            TreeNode left = root.left;
            TreeNode right = root.right;
            flatten(right);
            TreeNode pre = findTail(left);
            flatten(left);
            pre.right = right;
            root.right = left;
            root.left = null;
        }
    }

    // 找到中序遍历下的最后一个节点
    private TreeNode findTail(TreeNode root) {
        if (root.left == null && root.right == null) return root;
        if (root.left == null) return findTail(root.right);
        if (root.right == null) return findTail(root.left);
        return findTail(root.right);
    }
}
